package com.future.mashibing;

import java.util.Arrays;

/**
 * Description:
 *
 * @author weiruibai.vendor
 * Date: 2021/10/26 09:19
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {4, 2, 5, 6, 11, 8};
        process(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 归并排序
     *
     * @param arr
     * @param L
     * @param R
     */
    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int M = L + ((R - L) >> 1);
        process(arr, L, M);
        process(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int L = l;
        int R = m + 1;
        int[] help = new int[r - l + 1];
        int index = 0;
        while (L <= m && R <= r) {
            help[index++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
        }
        while (L <= m) {
            help[index++] = arr[L++];
        }
        while (R <= r) {
            help[index++] = arr[R++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l++] = help[i];
        }
    }

}
